package leetcode.leetcode105;

import java.util.Arrays;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/27
 *
 * 根据前中序遍历树构建二叉树
 */
public class Leetcode105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        // 获取根据节点
        int rootValue = preorder[0];
        TreeNode root = new TreeNode(rootValue);
        // 区分左右子树
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                // 0 ~ i-1 为左子树 函数含头不含尾
                int[] inLeft = Arrays.copyOfRange(inorder, 0, i);
                // i+1 ~ inorder.length -1 为右子树
                int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);

                // 因为前序或中序子树节点数量相同，所以拷贝长度参照上面
                int[] preLeft = Arrays.copyOfRange(preorder, 1, i + 1);
                int[] preRight = Arrays.copyOfRange(preorder, i + 1, inorder.length);

                root.left = buildTree(preLeft, inLeft);
                root.right = buildTree(preRight, inRight);
                break;
            }
        }
        return root;
    }
}
